/**
 * 斐波那契数列
 */
function fun1(n: number): number {
    if (n <= 0) {
        return 0
    }
    if (n == 1) {
        return 1
    }
    return fun1(n-1) + fun1(n-2)
}
let start = new Date().getTime()
// fun1(40)
let end = new Date().getTime()
// console.log(`30 耗时：${end-start}ms`) // 15ms
// console.log(`40 耗时：${end-start}ms`) // 1551ms
// console.log(`50 耗时：${end-start}ms`) // 1551ms

function fun2(first: number, second: number, n: number): number {
    if (n <= 0) {
        return 0
    }
    if (n < 3) {
        return 1
    }
    else if (n == 3) {
        return first + second
    }
    else {
        return fun2(second, first + second, n-1)
    }
}
start = new Date().getTime()
fun2(1, 1, 100)
end = new Date().getTime()
// console.log(`40 耗时：${end-start}ms`) // 0ms
console.log(`60 耗时：${end-start}ms`) // 1ms